The invention pertains to methods and apparatus for encoding data in accordance with an NB/(N+1)B block code for transmission and to methods and apparatus for decoding the encoded data. The invention is particularly useful in communication environments in which the spectrum of the transmitted signal is significantly constrained, e.g., in high-speed, wired data transmission systems which require the spectrum of the transmitted signal to be restricted to as a narrow a band of high frequencies as possible, and to be free of a DC component.
Throughout the disclosure, including in the claims, the notation xe2x80x9cnB/mBxe2x80x9d code (or xe2x80x9cn-bit-to-m-bitxe2x80x9d code) is used to denote a block code in which n-bit symbols (input words) are encoded as m-bit code words, where m greater than n. For example, in a class of well-known conventional block codes are 8B/10B codes in wich 8-bit input words are encoded as 10-bit code words.
Throughout the disclosure, including in the claims, the term xe2x80x9csymbolxe2x80x9d is used synonymously and interchangeably with the expression xe2x80x9cinput word.xe2x80x9d
Throughout the disclosure, including in the claims, the expression xe2x80x9ctable lookupxe2x80x9d denotes a mapping operation that is implemented in any manner (not necessarily by searching a ROM or CAM type memory for an output value in response to an input value). For example, table lookup can be implemented using a memory-based lookup table or a logic-based lookup table, as a complex logic function (that performs the equivalent of a memory-based table lookup), as a logic truth table/Karnaugh map, or in any other suitable manner.
A digital communication channel imposes restrictions on the nature of the data it can carry. For example, during serial data transmission (transmission of a signal indicative of a bit sequence), sufficient transitions must be present to enable accurate clock and data recovery at the receiver, the DC component of the transmitted signal should be eliminated to prevent baseline wander, and the pass band frequency range should be minimized to reduce design complexity. To meet these requirements, conventional high-speed serial communication often transmits data that have been encoded using a conventional 8B/ 10B block code (e.g., the conventional code, sometimes referred to as the xe2x80x9cIBMxe2x80x9d 8B/10B code, described in U.S. Pat. No. 4,486,739, issued on Dec. 4, 1984). The IBM 8B/10B block code is DC-free, guarantees 3 transitions per code word, and ensures that the maximum run without a transition is 4 bits. However, an 8B/10B block code provides low channel utilization (only 80% of the channel capacity is available for application use). Communication protocols layered above this channel code further reduce channel capacity for carrying useful data.
To encode data using a block code, a sequence of user data bits is encoded as a larger number of bits according to a predetermined table or function. The added bits of overhead preferably ensure a high transition density to facilitate clock/data recovery, and accomplish DC balancing to maintain running disparity near zero, which enables the use of AC-coupling. Since the code space is larger than the data space, a modest error detection capability is also afforded.
Various serial links for transmitting data and clock signals are well known. One conventional serial link, used primarily for high-speed transmission of video data from a host processor (e.g., a personal computer) to a monitor, is known as a transition minimized differential signaling interface (xe2x80x9cTMDSxe2x80x9d link). The characteristics of a TMDS link include the following:
1. video data are encoded using an 8B/10B block code and transmitted as encoded words (each 8-bit word of digital video data is converted to an encoded 10-bit word before transmission):
a. the encoding determines a set of xe2x80x9cin-bandxe2x80x9d words and a set of xe2x80x9cout-of-bandxe2x80x9d words (the encoder can generate only xe2x80x9cin-band xe2x80x9d words in response to video data, although it can generate xe2x80x9cout-of-bandxe2x80x9d words in response to control or sync signals. Each in-band word is an encoded word resulting from encoding of one input video data word. All words transmitted over the link that are not in-band words are xe2x80x9cout-of-bandxe2x80x9d words);
b. the encoding of video data is performed such that the in-band words are transition minimized (a sequence of in-band words has a reduced or minimized number of transitions);
c. the encoding of video data is performed such that the in-band words are DC balanced (the encoding prevents each transmitted voltage waveform that is employed to transmit a sequence of in-band words from deviating by more than a predetermined threshold value from a reference potential. Specifically, the tenth bit of each xe2x80x9cin-bandxe2x80x9d word indicates whether eight of the other nine bits thereof have been inverted during the encoding process to correct for an imbalance between running counts of ones and zeroes in the stream of previously encoded data bits);
2. the encoded video data and a video clock signal are transmitted as differential signals (the video clock and encoded video data are transmitted as differential signals over conductor pairs);
3. three conductor pairs are employed to transmit the encoded video, and a fourth conductor pair is employed to transmit the video clock signal; and
4. signal transmission occurs in one direction, from a transmitter (typically associated with a desktop or portable computer, or other host) to a receiver (typically an element of a monitor or other display device).
A use of the TMDS serial link is the xe2x80x9cDigital Visual Interfacexe2x80x9d interface (xe2x80x9cDVIxe2x80x9d link) adopted by the Digital Display Working Group. A DVI link can be implemented to include two TMDS links (which share a common conductor pair for transmitting a video clock signal) or one TMDS link, as well as additional control lines between the transmitter and receiver.
A typical DVI link includes a transmitter, a receiver, and a cable comprising conductors connected between the transmitter and receiver. The conductors include a conductor pair for transmitting serialized data over one channel (Channel 0) from an encoder (in the transmitter) to a decoder (in the receiver), a conductor pair for transmitting serialized data over another channel (Channel 1) from another encoder in the transmitter to another decoder in the receiver, a conductor pair for transmitting serialized data over another channel (Channel 2) from a third encoder in the transmitter to third decoder in the receiver, and a conductor pair for transmitting a video clock over a fourth channel (Channel C) from the transmitter to the receiver. The conductors also include wires for a Display Data Channel (xe2x80x9cDDCxe2x80x9d) channel (which can be used for bidirectional I2C communication between the transmitter and receiver), a Hot Plug Detect (HPD) line (on which a monitor associated with the receiver transmits a signal that enables a processor associated with the transmitter to identify the monitor""s presence), xe2x80x9cAnalogxe2x80x9d lines for analog video transmission from the transmitter to the receiver, and xe2x80x9cPowerxe2x80x9d lines for provision of power from the transmitter to the receiver.
Each encoder in the transmitter encodes the data to be transmitted over one of Channels 0, 1, and 2, and serializes the encoded bits to be transmitted over the relevant channel. Each encoder responds to a control signal (an active high binary control signal referred to as a xe2x80x9cdata enablexe2x80x9d or xe2x80x9cDExe2x80x9d signal) by selectively encoding either digital video words (in response to DE having a high value) or a control or synchronization signal pair (in response to DE having a low value). Each of the encoders receives a different pair of control or synchronization signals: a first encoder receives horizontal and vertical synchronization signals (HSYNC and VSYNC); a second encoder receives control bits CTL0 and CTL1; and a third encoder receives control bits CTL2 and CTL3. Thus, each encoder generates in-band words indicative of video data (in response to DE having a high value), the first encoder generates out-of-band words indicative of the values of HSYNC and VSYN having a low value), the second encoder generates out-of-band words indicative of the values of CTL0 and CTL1 (in response to DE having a low value), and the third encoder generates out-of-band words indicative of the values of CTL2 and CTL3 (in response to DE having a low value). In response to DE having a low value, each of the second and third encoders generates one of four specific out-of-band words indicative of the values 00, 01, 10, or 11, respectively, of control bits CTL0 and CTL1 (or CTL2 and CTL3).
Another serial link is the xe2x80x9cHigh Definition Multimedia Interfacexe2x80x9d interface (xe2x80x9cHDMIxe2x80x9d link) developed by Silicon Image, Inc., Matsushita Electric, Royal Philips Electronics, Sony Corporation, Thomson Multimedia, Toshiba Corporation, and Hitachi. It has been proposed to transmit encrypted video and audio data over an HDMI link.
Another serial link (sometimes referred to as a xe2x80x9cSATAxe2x80x9d link) complies with the standard known as Serial ATA, Revision 1.0, adopted on Aug. 29, 2001, by the Serial ATA Working Group, for communication between a host and storage device. A host can be coupled to each of one or more storage devices, with a SATA link between the host and each storage device.
Other serial links differ from TMDS links by encoding data as N-bit code words that are not 10-bit TMDS code words, or by transmitting encoded video over more than three or less than three conductor pairs, or in other ways.
The term xe2x80x9ctransmitterxe2x80x9d is used herein in a broad sense to denote any device capable of encoding data and transmitting the encoded data over a serial link (and optionally also performing additional functions, which can include encrypting the data to be transmitted and other operations related to encoding, transmission, or encryption of the data). The term xe2x80x9creceiverxe2x80x9d is used herein in a broad sense to denote any device capable of receiving and decoding data that has been transmitted over a serial link (and optionally also performing additional functions, which can include decrypting the received data and other operations related to decoding, reception, or decryption of the received data). For example, the term transmitter can denote a transceiver that performs the functions of a receiver as well as the functions of a transmitter. For another example, in a system including two transceivers which communicate via a serial link, each transceiver can be both a receiver and a transmitter.
The data transmitted between the transmitter and receiver of a serial link can, but need not, be transmitted differentially (over a pair of conductors). Also, although a TMDS link has four differential pairs (in the single pixel version), three for video data and the other for a video clock, other serial links include a different number of conductors or conductor pairs.
Typically, the primary data transmitted by a TMDS link are video data. What is often significant about this is that the video data are not continuous, and instead have blanking intervals. These blanking intervals provide an opportunity for auxiliary data to be transported, and they represent unused bandwidth. However, many serial links do not transmit data having blanking intervals, and thus do not encode input data (for transmission) in response to a data enable signal. For example, audio serial links would typically transmit continuous data.
The term xe2x80x9cstreamxe2x80x9d of data, as used herein, denotes that all the data are of the same type and are transmitted with the same clock frequency. The term xe2x80x9cchannel,xe2x80x9d as used herein, refers to a portion of a serial link that is employed to transmit data serially (e.g., a particular conductor or conductor pair between the transmitter and receiver over which the data are transmitted serially, and specific circuitry within the transmitter and/or receiver used for transmitting and/or recovery of the data) and to the technique employed to transmit the data over the link.
It is known to encode input words in accordance with an NB/(N+1)B block code, and to transmit the resulting (N+1)-bit code words over a serial link. For example, U.S. Pat. No. 6,198,413, issued on Mar. 6, 2001, teaches use of a 7B/8B block code with a 9B/10B block code, with concatenation of the resulting 8 and 10 bit code words to implement 16B/18B encoding. U.S. Pat. No. 6,198,413 suggests (at col. 10, line 51 to col. 11, line 22) generation of some of the code words by logic circuitry (e.g., circuitry that appends a zero or one to a 9-bit input word to generate a 10-bit code word), but that table lookup may need to be used to generate other ones of the code words where logic circuitry for doing so cannot readily be implemented. It also suggests (at col. 11, lines 25-30) use of two sets of logic circuitry for encoding (e.g., logic circuitry for appending a zero or one to some 9-bit input words to generate 10-bit code words, and other logic circuitry which inverts some bits of other 9-bit input words and performs some other logical operation on each resulting 9-bit word to generate a 10-bit code word). It also teaches (e.g., with reference to XOR gates 4008 and 4010 of FIG. 4) an encoding method in which two different codebooks are used to encode each input word of an input word sequence, and a code word is chosen from one codebook (rather than the other) to encode each input word such that the chosen code word will not increase running disparity (and will thus tend to promote DC balance) of a code word sequence indicative of the input word sequence.
However, U.S. Pat. No. 6,198,413 does not teach an automated, robust method for choosing an NB/(N+1)B code, or a method for choosing an NB/(N+1)B code so that table lookup is used only rarely (if ever) during encoding of an input word sequence.
In preferred embodiments, the invention is a method and apparatus for encoding N-bit input words using a block code to generate (n+1)bit code words. Preferably, xe2x80x9cNxe2x80x9d is an odd integer (e.g., N=7 or N=9). In some preferred embodiments, (N+M)-bit input words are encoded to generate (N+N+2)-bit code word, using a first block code to encode an N-bit fragment of each input word as an (N+1)-bit code word, using a second block code to encode the remaining M bits of the input word as an (M+1)-bit code word, and concatenating the (N+1)-bit code word with the (M+1)-bit code word. Preferably, xe2x80x9cNxe2x80x9d and xe2x80x9cMxe2x80x9d are odd integers.
Block coding in accordance with the invention can provide spectral properties similar to those provided by conventional 8B/10B coding while reducing the channel coding overhead (e.g., to about 10% for a 9B/10B code from about 20% for a conventional 8B/10B code). This provides greater channel capacity for application use, thereby increasing the effective bandwidth of the communication link. Alternatively, the savings from the reduced overhead is redeployed (e.g., by transmitting control bits and/or special characters with the encoded data) to create an enhanced physical and link layer that provides higher level communication protocol functionality (communication protocol functionality at at least one level higher than the link level).
To implement preferred embodiments of the invention, the N most desirable (N+1)-bit code words having disparity greater than or equal to zero (i.e., the N most desirable code words that have more ones than zeros, or an equal number of ones and zeros) are selected to determine a xe2x80x9cpositivexe2x80x9d codebook (each N-bit input word is mapped to one of the code words in the positive codebook). A xe2x80x9cnegativexe2x80x9d codebook, including the complement of each code word in the positive codebook, is also determined. Each code word in the negative codebook has disparity less than or equal to zero, and each of the N-bit input words is mapped to one of the code words in the negative codebook. The code words are chosen so that, for most input words, a simple systematic mapping to an (N+1)-bit code word in the positive codebook exists and can be implemented by simple logic circuitry (e.g., to force a transition with the added bit). During encoding, the other N-bit input words (typically only a small subset of the full set of N-bit symbols) can be replaced by code words of the positive codebook via table lookup. The resulting code words from the positive codebook are then replaced by their complements (members of the negative codebook) as necessary to maintain DC balancing.
When using positive and negative codebooks in which each code word has an even number of bits, code words of neutral disparity (disparity equal to zero) can occur in both codebooks. If each code word has an odd number of bits, each codebook would include only code words with strictly positive (or strictly negative) disparity. In the latter case, the codebooks would be forced to contain disjoint halves of the code space and the spectrum could not be deterministically controlled. Thus, in preferred implementations of NB/(N+1)B coding in accordance with the invention, N is an odd number. However, such codes do not have good affinity with 8-bit data that is typically used in computer systems. If this issue increases the implementation complexity beyond a reasonable measure, two such codes can be used together to form less dense code spaces that possess better alignment with 8-bit data. For example, 9B/10B and 7B/8B codes can be used together to form a 16B/ 18B code, by concatenating 8-bit and 10-bit code words generated in accordance with the 9B/10B and 7B/8B codes to generate 18-bit code words.
Preferred embodiments of the invention take advantage of the typical case that most of the N-bit input words exhibit the desired spectral properties by implementing a simple, systematic mapping of each such input word to an (N+1)-bit code word (preferably using simple logic circuitry). The input words that do not exhibit desired spectral properties are mapped to code words with more complex functions or via a simple table.
In preferred embodiments, the invention is a method for selecting positive and negative codebooks that are complements of each other that includes the following steps. Selection of the positive codebook begins by eliminating all candidate code words having negative disparity. The remaining candidate code words are then filtered, preferably in automated fashion (e.g., by a programmed computer) based on predetermined spectral properties to select a subset of the candidate code words that determines the positive codebook. For example, simple filters eliminate each of the candidate code words having transition density below a predetermined transition density, each of the candidate code words having disparity greater than a predetermined disparity, and each of the candidate code words having a transition-free run of length that exceeds a predetermined maximum run length. Spectral analysis of the code space can be used to rank the potential code words and select only those above a particular threshold for inclusion in the codebook. For example, code words with runs greater than 5, transition density less than 30%, or disparity greater than 4 can be eliminated. The code words of the positive codebook are then selected from the remaining candidate code words to determine a bijective (injective, in the sense that when f(x1)=f(x2), it is true that x1=x2, and positive codebook. For each input symbol, the code word in the negative codebook is then identified as the complement of the code word in the positive codebook for the input symbol.
In variations, the positive and negative codebooks are not strictly complements of each other. For example, in some embodiments, the code words of the negative codebook having nonzero disparity are complements of corresponding code words of the positive codebook, but the code words of the negative codebook that have zero disparity are identical to (they are not complements of) corresponding code words of the positive codebook.
In preferred embodiments, a mapping is defined from input words to a xe2x80x9cpositivexe2x80x9d codebook containing only code words of neutral or positive disparity, and the mapping of each code word of the positive codebook to a code word of a corresponding xe2x80x9cnegativexe2x80x9d codebook is determined simply by complementing the former code word to generate the latter code word. Alternatively, the mapping of each code word (having nonzero disparity) of the positive codebook to a code word of a corresponding xe2x80x9cnegativexe2x80x9d codebook is determined by complementing the former code word to generate the latter code word, and each code word (having zero disparity) of the positive codebook is identical to a corresponding code word of the xe2x80x9cnegativexe2x80x9d codebook. Ideally, for each codebook, a mapping function from the input words to the code words (of the codebook) is found that is bijective and simple to implement using logic circuitry. However, even if such an ideal mapping function cannot be found, a simple mapping function can typically be identified that covers a large subset of the input symbol space, and the remaining input symbols are handled as special cases (e.g., special input symbols for which encoding must be accomplished using look up tables).
Preferred embodiments in which most input words meet the desired spectral constraints employ a straightforward mapping that systematically concatenates a bit of predetermined value (e.g. a zero bit) with (e.g., prepends or appends the bit to) each input word to form a code word, or systematically inserts a bit of predetermined value (e.g. a zero bit) in a predetermined position among the bits of each input word to form a code word. Possibilities for such mapping functions include inserting a bit so that symbol disparity becomes more positive (and complementing the resulting code word if its disparity is negative) and inserting a bit so that symbol disparity approaches zero (complementing the resulting code word if its disparity is negative). Many other mappings are also possible. The selection of a mapping depends on its symbol coverage and implementation complexity. For small code spaces, the exemplary mappings set forth in this paragraph can provide coverage of roughly 80% of the input words, while requiring only simple logic circuitry to implement.
The input words for which a straightforward mapping (implementable by simple logic circuitry) fails will typically significantly violate the spectral constraints (e.g., they will have very low transition density). These symbols can be subjected to a secondary mapping technique that applies a more complex function. For example, the secondary mapping could perform alternate bit inversion for symbols with low transition density, complementing the resulting code word if its disparity is negative. The implementation cost of the secondary mapping must be weighed against the cost of simply handling all the unmapped symbols as special cases, using a simple implementation structure such as a lookup table.
When the secondary mapping is accomplished by table lookup, the mapping can be arbitrarily complex. This gives greater flexibility to the mapping process. For example, code words can be selected so as to minimize the magnification of bit errors in the encoded data stream.
In a class of embodiments, the invention is a communication system including two endpoints (e.g., a transmitter and receiver or two transceivers) and a serial link (having at least one channel) between the endpoints, at least one of the endpoints is configured to generate encoded data by encoding input words in accordance with a line code and to transmit the resulting code words over each of one or more channels of the link to the other endpoint, and the line code specifies an NB/(N+1)B block code for encoding the input words. Typically, the line code also specifies special characters that are distinguishable from bit sequences of the transmitted code words. Another aspect of the invention is an endpoint device (i.e., a transmitter, receiver, or transceiver) configured to generate encoded data in accordance with a line code (where the line code specifies an NB/(N+1)B block code for encoding input words, and typically also specifies special characters) and to transmit the encoded data over a serial link, and/or to receive and decode such encoded data after the encoded data have propagated over a serial link.
Other aspects of the invention are methods for generating encoded data in accordance with a line code (where the line code specifics an NB/(N+1)B block code for encoding input words, and typically also specifies special characters), methods for decoding such encoded data, and methods for determining a set of code words (e.g., positive and negative codebooks) for implementing such a block code.